/**
 * @author ChaP
 * @date 2019/05/09
 * @describe:
 */
package CodingTest.AC20190509;

import java.util.ArrayList;
import java.util.List;

/**
 * leetcode-417
 * 给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。

 规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。

 请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。



 提示：

 输出坐标的顺序不重要
 m 和 n 都小于150


 示例：



 给定下面的 5x5 矩阵:

 太平洋 ~   ~   ~   ~   ~
 ~  1   2   2   3  (5) *
 ~  3   2   3  (4) (4) *
 ~  2   4  (5)  3   1  *
 ~ (6) (7)  1   4   5  *
 ~ (5)  1   1   2   4  *
 *   *   *   *   * 大西洋

 返回:

 [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).
 */
public class pacificAtlantic {
    public List<int[]> pacificAtlantic(int[][] matrix){
        List<int[]> res = new ArrayList<>();
        if(matrix == null || matrix.length ==0||matrix[0].length==0){
            return res;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        boolean[][]Pacific = new boolean[row][col];
        boolean[][]Atlantic = new boolean[row][col];
        //从四周开始深搜
        for(int i=0;i<row;i++){
            dfs(matrix,Pacific,Integer.MIN_VALUE,i,0);
            dfs(matrix,Atlantic,Integer.MIN_VALUE,i,col-1);
        }
        for(int i =0;i<col;i++){
            dfs(matrix,Pacific,Integer.MIN_VALUE,0,i);
            dfs(matrix,Atlantic,Integer.MIN_VALUE,row-1,i);
        }
        //求两个交集，即为结果
        for(int i =0;i<row;i++){
            for(int j = 0;j<col;j++){
                if(Pacific[i][j] && Atlantic[i][j]){
                    int[] temp = new int[2];
                    temp[0]=i;
                    temp[1]=j;
                    res.add(temp);
                }
            }
        }
return res;
    }
    public void dfs(int[][] matrix,boolean[][] visited,int height,int x,int y){
      int row = matrix.length;
        int col = matrix[0].length;
        if(x<0||x>=row||y<0||y>=col||matrix[x][y]<height||visited[x][y]){
            return;
        }
        visited[x][y] = true;
        dfs(matrix,visited,matrix[x][y],x+1,y);//向右
        dfs(matrix,visited,matrix[x][y],x-1,y);//向左
        dfs(matrix,visited,matrix[x][y],x,y-1);//向上
        dfs(matrix,visited,matrix[x][y],x,y+1);//向上
    }
}
